Thread: 2^k

I have written a program to check if a number can be expressed in the form 2^k.
The program is not showing the correct output.

Code:

#include<stdio.h>
int check(float n);
int main()
{
    float n;
    int i;
    scanf("%f",&n);
	//i=s(n);
    //printf("\n\n%d\n\n",i);
    if(check(n)==1)
    {
		printf("\nIt is of the form 2^k");
	}
    else
	{
		printf("\nIt is not of the form 2^k");
	}
	return 0;
}
int check(float n)
{
	float x;
	x=n/2.0;
	//printf("\n%f",x);
	if(x!=2.0)
	{
		if(x<2.0)
			return 0;
		else
			check(x);
	}
	else
		return 1;
}

The return value of function check() is giving some garbage value.Can you find it out?
Thanks

Forgot to return from function?
return check(x);

If you are using gcc, gcc -Wall will emit warning. Or you can use splint.

in function "check", all paths are not returing values. Hence you should get the garbage value. as told by bayin, you should return the check value in the else part of your program.

Originally Posted by anandvn

in function "check", all paths are not returing values. Hence you should get the garbage value. as told by bayin, you should return the check value in the else part of your program.

Yes exactly Bayint and anandvn, i dint place a return statement for check(x).Thank you for pointing it out, now it works fine.
But how does the absence of return affecting it, since without return statement also the function is being called and invoked recursively?

Originally Posted by dwks

Using floating-point equality comparisons is risky. See e.g. Why don't floating point comparisons work?: C / C++ FAQs & Programming Resources - ProkutFAQ
It's best to compare within a small epsilon value to account for floating-point error, especially in chained calculations such as you have (divide by two, divide by two, ...).

Also, you could do the same thing more simply with something like this.

Code:

#define EPSILON 0.0001

int isPowerOf2(double number) {
    double logarithm = log(number) / log(2.0);

    double intpart;  /* don't care about this value, just throwing it away */
    double floatpart = modf(logarithm, &intpart);

    return (floatpart < EPSILON);
}

I'm using the change of base rule here to obtain the logarithm base two of the supplied number. (Note that log() actually uses base e.) If this number is 2.000 or 3.000 or any integer, then the original number was a power of 2. I use modf() to obtain the floating-point part of the number and ensure that this is less than some small epsilon number, essentially that it is an integer.

You could generalize this to check for other bases as well. And I didn't know this function existed until I was writing this post, but this could even be done with frexp().

Just some food for thought . . . .

yeah the logarithm way is fine, simple and short. I tried it out and is better than the recursive way. I didn't have the idea of modff() function but I learnt from this now. It was really fun to find this interesing way of doing with log().Thanks.

Sorry for late reply dude....my connection was having some problem

I did it like this:

Code:

#include<stdio.h>
#include<math.h>
int ispowerof2(float n);
int main()
{
    float n;
    scanf("%f",&n);
    if(ispowerof2(n)==1)
    {
		printf("\nIt is of the form 2^k");
	}
    else
	{
		printf("\nIt is not of the form 2^k");
	}
	return 0;
}
int ispowerof2(float n)
{
	float logarithm,fpart;
	logarithm=log10(n)/log10(2.0);//log2(n) =log10(n) * log2(10) =log10(n)/log10(2)
	float ipart;
	fpart=modff(logarithm,&ipart);
	//printf("\nfpart=%f",fpart);
	if(modff(logarithm,&ipart)==0.0)
		return 1;
	else
		return 0;
}

Originally Posted by rakeshkool27

But how does the absence of return affecting it, since without return statement also the function is being called and invoked recursively?

You are just getting lucky. I ran your program using Visual C++ on an Intel machine and looked at the disassembly. Your main call to "check(n)" sets the return value to the contents of the EAX register, which happens to contain the return value of your last recursive call.

Originally Posted by dwks

I use modf() to obtain the floating-point part of the number and ensure that this is less than some small epsilon number, essentially that it is an integer.

I don't think a logarithm based solution is going to work. First of all, you'd have to choose a smaller EPSILON than you've chosen, to cover a value as large as 2^53-1, for example. On top of that, you are going to lose precision on the logarithm calculation for such large numbers. I tried "isPowerOf2(9007199254740991.0)" (2^53-1) and floatpart always comes out 0. No EPSILON is going to work in this case. It incorrectly thinks that it is a power of two.

rakeshkool27,

I think we should go back to your original "repeated division by 2" idea and make it work. I modified your "check()" function to use modf but without logarithms (don't forget to include math.h):

Code:

int check (float x)
{
 double intpart, fracpart;

 if (x == 1)
   return 1;
 else
 {
  x = x/2.0f;
  fracpart = modf(x, &intpart);
  if (fracpart == 0)
    return(check(x));
  else
    return(0);
 }
}

This will correctly classify all integers between 1 and 2^24 (change to use doubles and you'll get up to 2^53).

You might find my article on checking for powers of two enlightening: Ten Ways to Check if an Integer Is a Power Of Two in C - Exploring Binary (specifically, see algorithm 1, "Divide by Two"),

Originally Posted by DoctorBinary

rakeshkool27,

I think we should go back to your original "repeated division by 2" idea and make it work. I modified your "check()" function to use modf but without logarithms (don't forget to include math.h):

Code:

int check (float x)
{
 double intpart, fracpart;

 if (x == 1)
   return 1;
 else
 {
  x = x/2.0f;
  fracpart = modf(x, &intpart);
  if (fracpart == 0)
    return(check(x));
  else
    return(0);
 }
}

This will correctly classify all integers between 1 and 2^24 (change to use doubles and you'll get up to 2^53).

You might find my article on checking for powers of two enlightening: Ten Ways to Check if an Integer Is a Power Of Two in C - Exploring Binary (specifically, see algorithm 1, "Divide by Two"),

I seem to be there are many ways to solve out this problem as I found in Ten Ways to Check if an Integer Is a Power Of Two in C - Exploring Binary.
So repeated division by two is also a preferred method and the easiest way that comes to my mind.I checked my modified program and is further more efficient than the log search way.

Thanks,once again.